#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    bool is_valid(vector<string> &board, int row, int col, int n)
    {
        // same col
        for (int i = 0; i < row; i++)
        {
            if (board[i][col] == 'Q')
            {
                return false;
            }
        }

        // 45
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        {
            if (board[i][j] == 'Q')
            {
                return false;
            }
        }

        // 135
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        {
            if (board[i][j] == 'Q')
            {
                return false;
            }
        }

        return true;
    }
    void tracebacking(int n, vector<string> &board, int row)
    {
        if (row == n)
        {
            res.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++)
        {
            if (is_valid(board, row, col, n))
            {
                board[row][col] = 'Q';
                tracebacking(n, board, row + 1);
                board[row][col] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n)
    {
        res.clear();
        vector<string> board(n, string(n, '.'));
        tracebacking(n, board, 0);
        return res;
    }
    vector<vector<string>> res;
};

int main()
{
    Solution sol;
    vector<vector<string>> res = sol.solveNQueens(4);
    for (auto result : res)
    {
        for (auto str : result)
        {
            cout << str << endl;
        }
        cout << endl;
    }
    return 0;
}